/**
 * \file Queue.h
 * \brief Queue definition and declaration class
 * \author Edouard ROGE
 * \date 13 september 2012
 */

#include "ArrayBase.h"

#ifndef _QUEUE_
#define _QUEUE_

/**
 * \class Queue
 * \brief Queue class with template, similar to std::queue<T>
 */
template <class T>
class Queue : public ArrayBase<T>
{
public:

	/**
	 * \fn Queue();
	 * \brief Default constructor
	 */
	Queue();

	/**
	 * \fn Queue(uint32 _iSize);
	 * \param _iSize new array's size
	 * \brief constructor, Resize array with the size in param
	 */
	Queue(uint32 _iSize);

	/**
	 * \fn Queue(const Queue<T> & _tQueue);
	 * \param _tQueue array to copy
	 * \brief Copy constructor
	 */
	Queue(const Queue<T> & _tQueue);

	/**
	 * \fn ~Queue();
	 * \brief Destructor
	 */
	~Queue();

	/**
	 * \fn void Enqueue(const T & _element);
	 * \param _element element added
	 * \brief add an element a the end of the queue
	 */
	void Enqueue(const T & _element);

	/**
	 * \fn T Dequeue();
	 * \return first element added
	 * \brief remove the first added element
	 */
	T Dequeue();

	/**
	 * \fn Queue<T> & operator = (const Queue<T> & _tQueue);
	 * \param _tQueue array to copy
	 * \return (*this) with new values
	 * \brief operator =
	 */
	Queue<T> & operator = (const Queue<T> & _tQueue);

	/**
	 * \fn template < class S > friend bool operator == (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);
	 * \param _tQueue1 Queue1
	 * \param _tQueue2 Queue2
	 * \return true if Queue1 is equal to Queue2
	 * \brief operator ==
	 */
	template < class S > friend bool operator == (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);

	/**
	 * \fn template < class S > friend bool operator != (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);
	 * \param _tQueue1 Queue1
	 * \param _tQueue2 Queue2
	 * \return true if Queue1 is not equal to Queue2
	 * \brief operator !=
	 */
	template < class S > friend bool operator != (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);

private:

	/** index of the first element */
	uint32 m_iFirstElement;
};


template< class T >
Queue<T>::Queue()
: ArrayBase<T>(), m_iFirstElement(0)
{
}

template< class T >
Queue<T>::Queue(uint32 _iSize)
: ArrayBase<T>(_iSize), m_iFirstElement(0)
{
}

template< class T >
Queue<T>::Queue(const Queue<T> & _tQueue)
: m_iFirstElement(0)
{
	_Clone(_tQueue.m_tArray, _tQueue.m_iSize);
}

template< class T >
Queue<T>::~Queue()
{

}

template< class T >
Queue<T> & Queue<T>::operator = (const Queue<T> & _tQueue)
{
	_Clone(_tQueue.m_tArray, _tQueue.m_iSize);
	m_iFirstElement = _tQueue.m_iFirstElement;
	return (*this);
}

template< class T >
void Queue<T>::Enqueue(const T & _element)
{
	if(ArrayBase<T>::m_iCapacity==0)
	{
		ArrayBase<T>::m_iCapacity = 1;
		ArrayBase<T>::m_tArray = (T*)MemoryPoolManager::GetInstance().Allocate(1 * sizeof(T));
		new(ArrayBase<T>::m_tArray)T();
	}
	else if(ArrayBase<T>::m_iSize==ArrayBase<T>::m_iCapacity)
	{
		ArrayBase<T>::m_iCapacity*=2;
		T * tArrayTemp = (T*)MemoryPoolManager::GetInstance().Allocate(ArrayBase<T>::m_iCapacity * sizeof(T));
		for(uint32 i = 0; i < ArrayBase<T>::m_iCapacity; ++i)
			new(tArrayTemp+i)T;

		if(m_iFirstElement==0)
		{
			memcpy(tArrayTemp, ArrayBase<T>::m_tArray, sizeof(T) * ArrayBase<T>::m_iSize );
		}
		else
		{
			memcpy(tArrayTemp, ArrayBase<T>::m_tArray, sizeof(T) * m_iFirstElement );
			memcpy(tArrayTemp+ArrayBase<T>::m_iCapacity-(ArrayBase<T>::m_iSize-m_iFirstElement), ArrayBase<T>::m_tArray+m_iFirstElement, sizeof(T) * (ArrayBase<T>::m_iSize-m_iFirstElement) );
			m_iFirstElement = ArrayBase<T>::m_iCapacity-(ArrayBase<T>::m_iSize-m_iFirstElement);
		}
		MemoryPoolManager::GetInstance().Free(ArrayBase<T>::m_tArray);
		ArrayBase<T>::m_tArray = tArrayTemp;
	}
	ArrayBase<T>::m_tArray[(m_iFirstElement+ArrayBase<T>::m_iSize)%ArrayBase<T>::m_iCapacity] = _element;
	++ArrayBase<T>::m_iSize;
}

template< class T >
T Queue<T>::Dequeue()
{
	T res = ArrayBase<T>::m_tArray[m_iFirstElement];
	ArrayBase<T>::m_tArray[m_iFirstElement].~T();
	m_iFirstElement = (m_iFirstElement+1)%ArrayBase<T>::m_iCapacity;
	--ArrayBase<T>::m_iSize;

	return res;
}

/**
 * \fn template < class S > bool operator == (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);
 * \param _tQueue1 Queue1
 * \param _tQueue2 Queue2
 * \return true if Queue1 is equal to Queue2
 * \brief operator ==
 */
template < class S >
bool operator == (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2)
{
	uint32 iSize1 = _tQueue1.Size();
	if( iSize1 == _tQueue2.Size() )
	{
		if(_tQueue1.m_iFirstElement!=_tQueue2.m_iFirstElement)
			return false;

		for(uint32 i=0; i < iSize1; ++i)
			if( _tQueue1[i] != _tQueue2[i] )
				return false;

		return true;
	}

	return false;
}

/**
 * \fn template < class S > bool operator != (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2);
 * \param _tQueue1 Queue1
 * \param _tQueue2 Queue2
 * \return true if Queue1 is not equal to Queue2
 * \brief operator !=
 */
template < class S >
bool operator != (const Queue<S> & _tQueue1, const Queue<S> & _tQueue2)
{
	return !(_tQueue1==_tQueue2);
}

#endif // _QUEUE_
